package main

import "math"

func numSquares(n int) int {
	dp := make([]int, n+1)
	dp[0] = 0
	for i := 1; i <= n; i++ {
		minVal := math.MaxInt
		for j := 1; j*j <= i; j++ {
			if dp[i-j*j] < minVal {
				minVal = dp[i-j*j]
			}
		}
		dp[i] = minVal + 1
	}
	return int(dp[n])
}
